Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph

Problem Statement

You are given a positive integer n. You are also given undirected graph containing 0 to n - 1 nodes, and 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

Return the count of unique node pairs where there's no path from one node to another.

Examples

Example 1:

  • Input: n = 4, edges = [[0, 1], [2, 3]]
Image
  • Expected Output: 4
  • Justification: The graph is divided into two disconnected parts: nodes 0 and 1 are connected, and nodes 2 and 3 are connected. The unreachable pairs are (0, 2), (0, 3), (1, 2), and (1, 3).

Example 2:

  • Input: n = 5, edges = [[0, 1], [2, 3]]
Image
  • Expected Output: 8
  • Justification: The unreachable pairs are (0, 2), (0, 3), (1, 2), (1, 3), (0, 4), (1, 4), (2, 4), and (3, 4).

Example 3:

  • Input: n = 3, edges = []
  • Expected Output: 3
  • Justification: With no edges, every node is isolated. Hence, all possible pairs are unreachable from each other: (0, 1), (0, 2), and (1, 2).

Solution

To solve this problem, we'll leverage depth-first search (DFS) to identify all connected components within the graph. By knowing the size of each connected component, we can calculate how many pairs of nodes within the same component can reach each other. Since the problem asks for unreachable pairs, we'll subtract the count of reachable pairs from the total possible pairs in the graph.

This approach is effective because it directly identifies the sizes of isolated sections in the graph, making it straightforward to compute the unreachable pairs by using combinatorial mathematics. The use of DFS ensures that we can efficiently traverse and mark all nodes in a connected component, thereby accurately calculating each component's size.

Step-by-Step Algorithm with Detailed DFS Steps

  1. Initialize Data Structures:

    • Create a HashMap called adj to store the adjacency list of the graph. This map associates each node with a list of its neighbors.
    • Initialize a boolean array named visit with a length of n (the number of nodes), with all elements set to false. This array tracks which nodes have been visited during DFS traversals.
  2. Build the Graph (Adjacency List):

    • For each edge [u, v] in the edges array, do the following:
      • Add v to the adjacency list of u and u to the adjacency list of v. This step ensures that the graph correctly represents all connections (edges) between nodes.
  3. Depth-First Search (DFS) to Find Component Sizes:

    • Define a recursive method dfs that takes a node node, the adjacency list adj, and the visited array visit. This method returns the size of the connected component that includes node.
    • Initialize a local variable count to 1, representing the current node.
    • Inside dfs, mark node as visited (visit[node] = true).
    • For each neighbor of node (accessible via adj.get(node)), if the neighbor has not been visited (!visit[neighbor]), recursively call dfs on the neighbor and add the result to count.
    • Return count at the end of dfs, representing the total size of the connected component found.
  4. Calculate Unreachable Pairs:

    • Initialize two long variables: numberOfPairs to store the final result, and remainingNodes to track the number of nodes not yet included in any connected component, initially set to n.
    • Iterate over all nodes i from 0 to n - 1. For each node i:
      • If visit[i] is false (node i has not been visited), call the dfs method starting from i. This call explores the entire connected component containing i, marks all nodes within it as visited, and returns the size of this component.
      • Use the size returned by dfs to update numberOfPairs. The formula numberOfPairs += sizeOfComponent * (remainingNodes - sizeOfComponent) calculates the number of new unreachable pairs formed by the current component and updates numberOfPairs accordingly.
      • Subtract the size of the current component from remainingNodes to reflect the reduced number of nodes available for forming pairs.
  5. Return the Total Number of Unreachable Pairs:

    • After iterating through all nodes and calculating unreachable pairs for each component, return numberOfPairs as the final result. This value represents the total number of pairs of nodes in the graph that cannot reach each other.

Algorithm Walkthrough

Let's consider the input: n = 5, edges = [[0, 1], [2, 3]].

  1. Initialization:

    • adj is an empty map, and visit is an array of false values of length 5.
  2. Build the Graph:

    • Add edge [0, 1] to adj: adj[0] now includes 1, and adj[1] includes 0.
    • Add edge [2, 3] to adj: adj[2] now includes 3, and adj[3] includes 2.
  3. Count Unreachable Pairs:

    • Start with i = 0, numberOfPairs = 0, and remainingNodes = 5.
    • Since visit[0] is false, perform DFS from node 0:
      • Visit nodes 0 and 1, marking them as visited. The DFS returns 2, the size of this component.
      • Update numberOfPairs += 2 * (5 - 2) = 6.
      • Update remainingNodes -= 2, now remainingNodes = 3.
    • Continue with i = 1 to i = 2. Node 1 is already visited, so move to node 2:
      • Perform DFS from node 2, visiting nodes 2 and 3. The DFS returns 2.
      • Update numberOfPairs += 2 * (3 - 2) = 2.
      • Update remainingNodes -= 2, now remainingNodes = 1.
    • For i = 3 and i = 4, nodes 3 is already visited, and when i = 4, no DFS is performed as it's disconnected from others, implicitly counting as a single-node component that doesn't add to numberOfPairs since its potential pairs have already been counted.
  4. Return Result:

    • The total numberOfPairs is (6 + 2 = 8), which is the final result returned by the method.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • DFS Traversal: The depth-first search (DFS) is performed for each node that hasn't been visited yet. Since each edge is visited exactly twice (once for each direction in the undirected graph), the time complexity for the DFS part is , where (V) is the number of vertices (nodes) and (E) is the number of edges in the graph.
  • Building the Adjacency List: The adjacency list is built by iterating through each edge once, leading to a time complexity of for this step.

Overall, the time complexity of the algorithm is , accounting for both the construction of the adjacency list and the DFS traversal.

Space Complexity

  • Adjacency List: The space complexity for storing the adjacency list is , as it needs to store a list of edges for each of the (V) vertices.
  • Visit Array: An additional space is used to keep track of which nodes have been visited during DFS.
  • DFS Call Stack: In the worst-case scenario, the depth of the call stack could be in the case of a deeply nested tree structure.

Hence, the total space complexity of the algorithm is , considering the storage requirements for the graph representation and the additional structures for managing DFS visits.

Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Single Number II (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm with Detailed DFS Steps

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity